| | Category | MA | P22 | Patterns in Transitive Relations |
| | Abstract | The question of how many transitive relations there are on a set with n |
| | elements is currently an open question in the field of mathematics. A |
| | transitive relation is a relation on a set such that, if (a, b) and (b, c) are in |
| | the relation, then (a, c) is also in the relation. The number of transitive |
| | relations on a set grows extremely rapidly as the number of elements |
| | increases. The number of transitive relations has only been counted for |
| | sets with sixteen or fewer elements. No formula for the number of |
| | transitive relations on a set is known, so it is as yet impossible to predict |
| | the number of transitive relations on a set. Answering this question is |
| | beyond the scope of the present project. However, this project does make |
| | some headway in identifying some specific types of transitive relations in |
| | an attempt to count some of the transitive relations on a set. |
| | In this study, patterns in transitive relations on sets with a small number of |
| | elements were analyzed and attempts were made to find generalizations |
| | from these patterns. These small sets were chosen because they are |
| | large enough to insights into the problem, yet small enough to be |
| | manageable. In examining transitive relations on these sets, several |
| | patterns emerged. Some theorems and conjectures were formulated that |
| | provide a starting point for answering the larger question about the |
| | number of transitive relations on a set with n elements. It is conjectured |
| | that any transitive relation with sufficiently many elements is almost |
| | reflexive (has not more than one non-reflexive relationship), where |
| | “sufficiently many” is a function of the cardinality of the set the relation is |
| | on. If true, this conjecture reduces the number of relations that must be |
| | considered when counting the transitive relations on a set. |
| | Bibliography | Ando, Kazutoshi. (2006). Extreme Point Axioms for Closure Spaces. |
| | Discrete Mathematics, 306(24), 3181-3188. |
| | Belunfante, Johan G. F. (2005). Thin Transitive Relations. Set Directory, 1- |
| | 6. |
| | Boros, Zoltán and Száz, Árpád. (2008). Reflexivity, Transitivity, Symmetry, |
| | and Anti-Symmetry of the Intersection Convolution of Relations. Rostock |
| | Mathematics Kolloq, 63, 55-62. |
| | Brinkmann, Gunnar and McKay, Brendan D. (2005). Counting Unlabelled |
| | Topologies and transitive Relations. Journal of Integer Sequences, 8, 1-7. |
| | |
| | Finch, Steven. (2003). Transitive relations, Topologies and Partial Orders. |
| | http//www. algo. inria. fr/bsolve/constant. html. Accessed on 28 |
| | December 2008. |
| | Ganzinger, Harald, Meyer, Christopher, and Veanes, Margua. (1999). The |
| | Two-Variable Guarded Fragment with Transitive Relations. http:// |
| | research. microsoft. com/apps/pubs. hmtl. Accessed on 10 January 2009. |
| | |
| | Libkin, Leonid. (1993). Direct Product Decompositions of Lattices, |
| | Closures, and Relation Schemes. Discrete Mathematics, 112, 119-138. |
| | Mossakowski, Till. (1998). Transitive Overloading Relations? http:// www. |
| | brics. dk/Projects. html. Accessed on 10 January 2009. |
| | Pfeiffer, Götz. (2004). Counting Transitive Relations. Journal of Integer |
| | Sequences, 7, 1-11. |
| | Physics Forums. (2009). Set Theory, Relations, Transitivity. http://www. |
| | physics forum. com. html. Accessed on 10 January 2009. |